{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find XOR Sum of All Pairs Bitwise AND"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #array #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数组 #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: getXORSum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #所有数对按位与结果的异或和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>列表的 <strong>异或和</strong>（<strong>XOR sum</strong>）指对所有元素进行按位 <code>XOR</code> 运算的结果。如果列表中仅有一个元素，那么其 <strong>异或和</strong> 就等于该元素。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，<code>[1,2,3,4]</code> 的 <strong>异或和</strong> 等于 <code>1 XOR 2 XOR 3 XOR 4 = 4</code> ，而 <code>[3]</code> 的 <strong>异或和</strong> 等于 <code>3</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>给你两个下标 <strong>从 0 开始</strong> 计数的数组 <code>arr1</code> 和 <code>arr2</code> ，两数组均由非负整数组成。</p>\n",
    "\n",
    "<p>根据每个 <code>(i, j)</code> 数对，构造一个由 <code>arr1[i] AND arr2[j]</code>（按位 <code>AND</code> 运算）结果组成的列表。其中 <code>0 &lt;= i &lt; arr1.length</code> 且 <code>0 &lt;= j &lt; arr2.length</code> 。</p>\n",
    "\n",
    "<p>返回上述列表的 <strong>异或和</strong> 。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>arr1 = [1,2,3], arr2 = [6,5]\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>列表 = [1 AND 6, 1 AND 5, 2 AND 6, 2 AND 5, 3 AND 6, 3 AND 5] = [0,1,2,0,2,1] ，\n",
    "异或和 = 0 XOR 1 XOR 2 XOR 0 XOR 2 XOR 1 = 0 。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>arr1 = [12], arr2 = [4]\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>列表 = [12 AND 4] = [4] ，异或和 = 4 。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= arr1.length, arr2.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= arr1[i], arr2[j] &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-xor-sum-of-all-pairs-bitwise-and](https://leetcode.cn/problems/find-xor-sum-of-all-pairs-bitwise-and/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-xor-sum-of-all-pairs-bitwise-and](https://leetcode.cn/problems/find-xor-sum-of-all-pairs-bitwise-and/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3]\\n[6,5]', '[12]\\n[4]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getXORSum(self, a: List[int], b: List[int]) -> int:\n",
    "        bit = 1\n",
    "        ans = 0\n",
    "        for t in range(32):\n",
    "            x = 0\n",
    "            y = 0\n",
    "            for i in a:\n",
    "                if i & bit:\n",
    "                    x += 1\n",
    "            for i in b:\n",
    "                if i & bit:\n",
    "                    y += 1\n",
    "\n",
    "            if (x * y) % 2:\n",
    "                ans += bit\n",
    "            bit *= 2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getXORSum(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        cnt1 = [0]*32\n",
    "        for num in arr1:\n",
    "            for j in range(32):\n",
    "                if num & (1<<j):\n",
    "                    cnt1[j] += 1\n",
    "\n",
    "        cnt2 = [0] * 32\n",
    "        for num in arr2:\n",
    "            for j in range(32):\n",
    "                if num & (1 << j):\n",
    "                    cnt2[j] += 1\n",
    "        ans = 0\n",
    "        for i in range(32):\n",
    "            cur = cnt1[i]*cnt2[i]\n",
    "            if cur % 2:\n",
    "                ans += 1<<i\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getXORSum(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        n=len(arr1)\n",
    "        cnt=[0]*31\n",
    "        for i in range(31):\n",
    "            for a in arr1:\n",
    "                if a>>i&1:\n",
    "                    cnt[i]+=1\n",
    "        ans=[0]*31\n",
    "        for a in arr2:\n",
    "            for i in range(31):\n",
    "                if a>>i&1:\n",
    "                    ans[i]+=cnt[i]\n",
    "        res=0\n",
    "        for i in range(31):\n",
    "            if ans[i]%2==1:\n",
    "                res|=1<<i\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getXORSum(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for i in range(max(*arr1, *arr2).bit_length()):\n",
    "            cnt = 0\n",
    "            for x in arr1:\n",
    "                if x & (1 << i):\n",
    "                    cnt += 1\n",
    "            if cnt & 1:\n",
    "                cnt = 0\n",
    "                for y in arr2:\n",
    "                    if y & (1 << i):\n",
    "                        cnt += 1\n",
    "                ans |= (cnt & 1) << i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getXORSum(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        n = len(arr1)\n",
    "        m = len(arr2)\n",
    "        arrXOR = 0 \n",
    "        for i in range(1,n):\n",
    "            arr1[i] = arr1[i-1]^arr1[i]\n",
    "        for j in range(1,m):\n",
    "            arr2[j] = arr2[j-1]^arr2[j]\n",
    "        arrXOR = arr1[n-1] & arr2[m-1]\n",
    "        return arrXOR"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getXORSum(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        m, n = len(arr1), len(arr2)\n",
    "        ans = 0\n",
    "        \n",
    "        # 依次确定答案二进制表示中的每一位\n",
    "        for k in range(30, -1, -1):\n",
    "            cnt1 = sum(1 for num in arr1 if num & (1 << k))\n",
    "            cnt2 = sum(1 for num in arr2 if num & (1 << k))\n",
    "            # 如果 cnt1 和 cnt2 都是奇数，那么答案的第 k 位为 1\n",
    "            if cnt1 % 2 == 1 and cnt2 % 2 == 1:\n",
    "                ans |= (1 << k)\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getXORSum(self, a: List[int], b: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for k in range(32, -1, -1):\n",
    "            # 统计每一个为上 1的个数\n",
    "            cnt1 = sum(1 for num in a if num >> k & 1)\n",
    "            cnt2 = sum(1 for num in b if num >> k & 1)\n",
    "            # 两个都为1\n",
    "            if cnt1 % 2 == 1 and cnt2 % 2 == 1:\n",
    "                ans |= (1 << k)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getXORSum(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        return reduce(lambda x, n: x^n, arr1) & reduce(lambda x, n: x^n, arr2)\n",
    "\n",
    "\n",
    "#a1&b1  a2&b1  a3&b1  a4&b1\n",
    "#a1&b2  a2&b2  a3&b2  a4&b2\n",
    "#a1&b3  a2&b3  a3&b3  a4&b3\n",
    "#a1&b4  a2&b4  a3&b4  a4&b4\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getXORSum(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        return reduce(xor, arr1) & reduce(xor, arr2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getXORSum(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        bits1 = [0] * 32\n",
    "        for a in arr1:\n",
    "            for i in range(32):\n",
    "                if (1 << i) & a:\n",
    "                    bits1[i] += 1\n",
    "\n",
    "        bits2 = [0] * 32\n",
    "        for a in arr2:\n",
    "            for i in range(32):\n",
    "                if (1 << i) & a:\n",
    "                    bits2[i] += 1\n",
    "\n",
    "        rst = 0\n",
    "        for i in range(32):\n",
    "            ones = bits1[i] * bits2[i]\n",
    "            if ones % 2:\n",
    "                rst += (1 << i)\n",
    "        return rst"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getXORSum(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        m, n = len(arr1), len(arr2)\n",
    "        t = reduce(ixor, arr2)\n",
    "        ans = 0\n",
    "        for num in arr1:\n",
    "            ans ^= num & t\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getXORSum(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        m, n = len(arr1), len(arr2)\n",
    "        ans = 0\n",
    "        \n",
    "        # 依次确定答案二进制表示中的每一位\n",
    "        for k in range(30, -1, -1):\n",
    "            cnt1 = sum(1 for num in arr1 if num & (1 << k))\n",
    "            cnt2 = sum(1 for num in arr2 if num & (1 << k))\n",
    "            # 如果 cnt1 和 cnt2 都是奇数，那么答案的第 k 位为 1\n",
    "            if cnt1 % 2 == 1 and cnt2 % 2 == 1:\n",
    "                ans |= (1 << k)\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getXORSum(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for i in range(31):\n",
    "            m = 0\n",
    "            cnt = 0\n",
    "            for x in arr1:\n",
    "                if x & (1 << i):\n",
    "                    cnt += 1\n",
    "            if cnt & 1:\n",
    "                cnt = 0\n",
    "                for y in arr2:\n",
    "                    if y & (1 << i):\n",
    "                        cnt += 1\n",
    "                ans |= (cnt & 1) << i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getXORSum(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        return reduce(xor, arr1) & reduce(xor, arr2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getXORSum(self, arr1: List[int], arr2: List[int]) -> int:        \n",
    "        M, N = len(arr1), len(arr2)\n",
    "        if M < N:\n",
    "            return self.getXORSum(arr2, arr1)\n",
    "        ans = 0\n",
    "        x = reduce(lambda n,x: x^n, arr1)\n",
    "        for i in range(N):\n",
    "            ans ^= arr2[i] & x\n",
    "        return ans\n",
    "\n",
    "\n",
    "#a1&b1  a2&b1  a3&b1  a4&b1\n",
    "#a1&b2  a2&b2  a3&b2  a4&b2\n",
    "#a1&b3  a2&b3  a3&b3  a4&b3\n",
    "#a1&b4  a2&b4  a3&b4  a4&b4\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getXORSum(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for i in range(31):\n",
    "            cnt = 0\n",
    "            for x in arr1:\n",
    "                if x & (1 << i):\n",
    "                    cnt += 1\n",
    "            if cnt & 1:\n",
    "                cnt = 0\n",
    "                for y in arr2:\n",
    "                    if y & (1 << i):\n",
    "                        cnt += 1\n",
    "                ans |= (cnt & 1) << i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getXORSum(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        m, n = len(arr1), len(arr2)\n",
    "        ans = 0\n",
    "        \n",
    "        # 依次确定答案二进制表示中的每一位\n",
    "        for k in range(30, -1, -1):\n",
    "            cnt1 = sum(1 for num in arr1 if num & (1 << k))\n",
    "            cnt2 = sum(1 for num in arr2 if num & (1 << k))\n",
    "            # 如果 cnt1 和 cnt2 都是奇数，那么答案的第 k 位为 1\n",
    "            if cnt1 % 2 == 1 and cnt2 % 2 == 1:\n",
    "                ans |= (1 << k)\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "    # 位运算\n",
    "    def getXORSum2(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        tot1 = reduce(xor, arr1)\n",
    "        tot2 = reduce(xor, arr2)\n",
    "        return tot1 & tot2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getXORSum(self, a: List[int], b: List[int]) -> int:\n",
    "        c = 0 \n",
    "        d = 0 \n",
    "        for j in a:\n",
    "            c^=j \n",
    "        for j in b:\n",
    "            d ^= j \n",
    "        return c&d\n",
    "\n",
    "        # return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getXORSum(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        tot1 = reduce(xor, arr1)\n",
    "        tot2 = reduce(xor, arr2)\n",
    "        return tot1 & tot2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\r\n",
    "由于 (a&b)^(a&c) == a&(b^c)，将两个数组的异或和求出，两个异或和的与就是答案。\r\n",
    "'''\r\n",
    "class Solution:\r\n",
    "    def getXORSum(self, a: List[int], b: List[int]) -> int:\r\n",
    "        return reduce(xor, a, 0) & reduce(xor, b, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getXORSum(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        \n",
    "        ans = 0\n",
    "        for k in range(30, -1, -1):\n",
    "            cnt1 = sum(1 if num & (1 << k) else 0 for num in arr1)\n",
    "            cnt2 = sum(1 if num & (1 << k) else 0 for num in arr2)\n",
    "            if cnt1 % 2 and cnt2 % 2:\n",
    "                ans += 1 << k\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getXORSum(self, a: List[int], b: List[int]) -> int:\n",
    "        return reduce(xor, a, 0) & reduce(xor, b, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getXORSum(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        tot1 = reduce(xor, arr1)\n",
    "        tot2 = reduce(xor, arr2)\n",
    "        return tot1 & tot2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def getXORSum(self, arr1: List[int], arr2: List[int]) -> int:\r\n",
    "        # a & b xor a & c = a & (b xor c)\r\n",
    "        res = 0 \r\n",
    "        tot2 = 0 \r\n",
    "        for x in arr2:\r\n",
    "            tot2 ^= x \r\n",
    "        for x in arr1:\r\n",
    "            res ^=  x & tot2 \r\n",
    "        return res \r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getXORSum(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        cnt1 = [0] * 30\n",
    "        for x in arr1:\n",
    "            for i in range(30):\n",
    "                if x & 1 << i:\n",
    "                    cnt1[i] += 1\n",
    "                    \n",
    "        cnt2 = [0] * 30\n",
    "        for x in arr2:\n",
    "            for i in range(30):\n",
    "                if x & 1 << i:\n",
    "                    cnt2[i] += 1\n",
    "        ret = 0\n",
    "        for i in range(30):\n",
    "            c = cnt1[i] * cnt2[i]\n",
    "            # print(i, c)\n",
    "            if c & 1:\n",
    "                ret |= 1 << i\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getXORSum(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for i in range(31):\n",
    "            m = 0\n",
    "            y1 = 0\n",
    "            for x in arr1:\n",
    "                y1 ^= x & (1 << i)\n",
    "            for y in arr2:\n",
    "                if y & (1 << i):\n",
    "                    m ^= y1\n",
    "            ans |= m\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getXORSum(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        l = reduce(xor, arr1)\n",
    "        r = reduce(xor, arr2)\n",
    "        return l & r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getXORSum(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        a = 0\n",
    "        b = 0\n",
    "        for i in arr1:\n",
    "            a ^= i \n",
    "        for j in arr2:\n",
    "            b ^= j\n",
    "        return a&b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getXORSum(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        n = max(max(arr1), max(arr2)).bit_length()\n",
    "        dic1, dic2 = [0]*n, [0]*n\n",
    "        for e in arr1:\n",
    "            for i in range(e.bit_length()):\n",
    "                if e & (1 << i):\n",
    "                    dic1[i] += 1\n",
    "        for e in arr2:\n",
    "            for i in range(e.bit_length()):\n",
    "                if e & (1 << i):\n",
    "                    dic2[i] += 1\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            if dic1[i]*dic2[i] % 2:\n",
    "                res += (1 << i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getXORSum(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        mp1 = defaultdict(int)\n",
    "        mp2 = defaultdict(int)\n",
    "        for x in arr1:\n",
    "            for i, c in enumerate(bin(x)[2:][::-1]):\n",
    "                if c == '1':\n",
    "                    mp1[i] += 1\n",
    "        for x in arr2:\n",
    "            for i, c in enumerate(bin(x)[2:][::-1]):\n",
    "                if c == '1':\n",
    "                    mp2[i] += 1\n",
    "        res = []\n",
    "        for i in range(100):\n",
    "            x, y = (mp1[i] * mp2[i]) % 2, (len(arr1) * len(arr2) - mp1[i] * mp2[i]) % 2\n",
    "            if (x == 0 and y == 0) or (x == 0 and y == 1):\n",
    "                res.append('0')\n",
    "            else:\n",
    "                res.append('1')\n",
    "\n",
    "        return int(''.join(res[::-1]), 2)\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
